The present invention relates generally to the field of computer networking and, more specifically, to the routing of packets within a computer network between a source node and a destination node.
The movement of data between source and destination nodes within a network is facilitated by routers, which develop pathways through a mesh of interconnections or links. While a mesh network provides redundant pathways to compensate for traffic loads or downed lines, the use of one pathway as opposed to another may be preferred for various reasons, such as speed, cost and congestion-avoidance. Routing protocols provide routers with the information required to create pathways through mesh networks based on routing information that is shared by routers.
A router may have a multiplicity of ports, and typically maintains routing tables (also known as forwarding tables) that indicate which port of the router a particular network address is located on. Routing protocols may broadly be classified as either static routing protocols, wherein routing pathways are specified by a network manager, or dynamic routing protocols, which rely on the router to collect information concerning the network and to build up-to-date routing tables. Routers periodically exchange routing tables with each other, and each router merges routing information to create new and updates routing tables.
Two common categories of dynamic routing protocols include distance-vector routing protocols and link-state routing protocols. Distance-vector routing protocols route packets based on the number of hops (or links) that must be traversed between a source node and a destination mode. Each hop (or link) is assigned a cost that identifies the distance between a routing node and its neighbors. The route that produces the least cost is selected as the propagation route. A popular distance-vector routing protocol is the Routing Information Protocol (RIP).
Link-state routing protocols are more sophisticated than distance-vector routing protocols and provide a greater degree of control over the routing process. For example, routes can be based on the avoidance of congested areas, the speed of links, the cost of using a link or various other criteria. The well-known Dijkstra algorithm is typically used to calculate routes based on a number of criteria including:
1. the number of hops between a source and destination node;
2. the speed of links between nodes;
3. delays caused by traffic congestion; and
4. the cost of a route, which is typically a metric defined by an administrator.
A popular link-state algorithm is the Open Shortest Path First (OSPF) protocol. The OSPF protocol is attractive in that an administrator can program pathways through a mesh network based on a traffic type. Further, OSPF routing tables updates only occur when necessary, rather than at predetermined intervals, thus reducing network traffic.
While the above protocols provide satisfactory results, they do not address phase delays and other factors introduced by mismatches in transmission speeds between links that constitute a possible pathway. Further, such protocols are not optimized for networks in which switched media dominates over shared media.
According to a first aspect of the invention, there is provided a method of routing traffic within a network including a plurality of nodes coupled by links. A set of metrics is determined for a corresponding set of links within the network. A linear optimization operation is performed utilizing the set of metrics to determine respective traffic flow values for links coupling a source node and a destination node within the network. Traffic within the network is routed according to the traffic flow values.
According to a second aspect of the invention, there is provided a network device configured to route network traffic as determined by a linear optimization operation performed using a set of metrics, corresponding to a set of links within the network.
Other features of the present invention will be apparent from the accompanying drawings and the detailed description that follows.